package subString;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author kunkun
 * @className LeetCode_239
 * @Description 求解滑动窗口最大值，
 * @date 2025/3/3 13:33
 */
public class LeetCode_239 {

    public int[] maxSlidingWindow(int[] nums, int k) {
//        return solution_1(nums,k);
//        return solution_2(nums,k);
        return solution_3(nums,k);
    }

    public static void main(String[] args) {
        LeetCode_239 object = new LeetCode_239();
//        object.print(object.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3));  //3 3 5 5 6 7
//        object.print(object.maxSlidingWindow(new int[]{1},1));  //1
        object.print(object.maxSlidingWindow(new int[]{1,3,1,2,0,5},3));  //3,3,2,5
    }

    public void print(int[] arrays){
        for (int array : arrays) {
            System.out.print(array+" ");
        }
        System.out.println();
    }

    /**
    * @Description: 方法1：暴力求解，时间复杂度：O（k*n），空间复杂度：O（1），超时
    * @Author: kunkun
    * @Date:  2025/3/3 13:44
    * @Parameters:
    * @Return
    * @Throws
    */
    public int[] solution_1(int[] nums, int k){
        //1. 定义返回变量
        int[] results = new int[nums.length - k + 1];

        //2. 暴力循环
        for (int i = 0; i < results.length; i++) {
            results[i]=maxInArrays(nums,i,k);
        }

        return results;
    }

    /**
    * @Description: 方法2：大根堆求解，时间复杂度：O（n*logk），空间复杂度：O（n），注意不能使用remove函数，remove时间复杂度：O（n）
    * @Author: kunkun
    * @Date:  2025/3/3 14:01
    * @Parameters:
    * @Return
    * @Throws
    */
    public int[] solution_2(int[] nums, int k){
        //1. 定义返回变量
        int[] results = new int[nums.length - k + 1];

        //2. 定义大根堆
        PriorityQueue<Integer[]> maxHeap = new PriorityQueue<>(new Comparator<Integer[]>() {    //int【】：value，index
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return o2[0]-o1[0];
            }
        });

        //3. 前期准备
        for (int i = 0; i < k-1; i++) {
            maxHeap.add(new Integer[]{nums[i],i});
        }

        //4. 循环遍历
        for (int i = k-1; i < nums.length; i++) {
            //4.1 新值入堆
            maxHeap.add(new Integer[]{nums[i],i});
            //4.2 旧值出堆
            while(maxHeap.peek()[1]<i-k+1){
                maxHeap.poll();
            }
            //4.3 堆顶入results
            results[i-k+1] = maxHeap.peek()[0];
        }

        return results;



    }


    /**
    * @Description: 方法3：单调队列求解，时间复杂度：O（n），空间复杂度：O（n）
    * @Author: kunkun
    * @Date:  2025/3/3 14:33
    * @Parameters:
    * @Return
    * @Throws
    */
    public int[] solution_3(int[] nums, int k){
        //1. 定义双端队列、返回结果
        LinkedList<Integer> queue = new LinkedList<>();
        int[] results = new int[nums.length - k + 1];

        //2. 基础准备
        for (int i = 0; i < k-1; i++) {
            addElement(queue,nums[i]);
        }
        //2. 循环遍历
        for (int i = k-1; i < nums.length; i++) {
            //2.1 入队
            addElement(queue,nums[i]);
            //2.2 出队
            deleteElement(queue,nums,i-k);
            //2.3 添加值
            results[i-k+1]=queue.getFirst();
        }

        return results;
    }

    //入队
    public void addElement(LinkedList<Integer> queue,int num){
        while(queue.size()!=0 && queue.getLast()<num){
            queue.pollLast();
        }
        queue.addLast(num);
    }

    //出队
    public void deleteElement(LinkedList<Integer> queue, int[] nums,int index){
        if (index<0){
            return;
        }
        if (nums[index]==queue.getFirst()){
            queue.pollFirst();
        }
    }



    private int maxInArrays(int[] nums, int i, int k) {
        int max=nums[i];
        for (int j = i+1; j < i+k && j < nums.length; j++) {
            if (max<nums[j]){
                max=nums[j];
            }
        }
        return max;
    }

}
